package com.LeetCode.dp.MatrixDP;

import org.junit.Test;

/**
 * 戳气球
 */
public class PokeTheBalloon {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // 两端加入两个虚拟气球
        int[] points = new int[n + 2];
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }

        int[][] dp = new int[n+2][n+2];

        for(int i = n; i>=0; i--){
            for(int j = i + 1; j<n+2; j++){
                for(int k = i + 1; k<j; k++){
                    dp[i][j] = Math.max(dp[i][j] ,
                                        dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);
                }
            }
        }

        return dp[0][n+1];

    }

    @Test
    public void test(){
        int[] arr = {3,1,5,8};
        System.out.println(maxCoins(arr));
    }
}
